import java.util.Date;
import java.util.GregorianCalendar;



public class MainClass {
	
	/**
	 * The method sorts an array of objects of the type Edge
	 * applying the eponymous algorithm.
	 * @param array
	 * @return
	 */
	public static int[] mergeSort(int[] array){
		if (array.length <= 1) return array;

		int middle = array.length/2;

		int[] left = new int [middle];
		int[] right = new int [array.length - middle];

		for (int i = 0; i < middle; i++)
			left[i] = array[i];
		for (int i = 0; i < right.length; i++)
			right[i] = array[i + middle];

		left = mergeSort(left);
		right = mergeSort(right);
		int[] result;
		if (left[left.length - 1] > right[0])
			result = merge(left, right);
		else {
			result = new int[left.length + right.length];
			for (int i = 0; i < left.length; i++)
				result[i] = left[i];
			for (int i = 0; i < right.length; i++)
				result[left.length + i] = right[i];
		}
		return result;
	}

	/**
	 * The method merges two sorted arrays and returns the merged array, which
	 * is also sorted
	 * @param left
	 * @param right
	 * @return
	 */
	public static int[] merge(int[] left, int[] right){

		int[] result = new int[left.length + right.length];
		int left_index = 0;
		int right_index = 0;

		// first, the two arrays are traversed simultaneously term at a time
		// the next free element in the result array is assigned the smaller value,

		while (left_index < left.length && right_index < right.length){
			if (left[left_index] <= right[right_index]){
				result[left_index + right_index] = left[left_index];
				left_index++;
			}
			else{
				result[left_index + right_index] = right[right_index];
				right_index++;
			}
		}

		if (left_index < left.length)
			for (left_index = left_index; left_index < left.length; left_index++) {
				result[left_index + right_index] = left[left_index];
			}


		else for (right_index = right_index; right_index < right.length; right_index++)
			result[left_index + right_index] = right[right_index];

		return result;


	}


	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("PROGRAMME STARTED!");
		int array_length = 1000;
		int [] test_array = new int [array_length];
		
		for (int i = 0; i < array_length; i++)
			test_array[i] = (int)(1000 * Math.random());
		
		long start = (new Date()).getTime();
		
		test_array = mergeSort(test_array);
		
		long stop = (new Date()).getTime();
		
		
		boolean array_sorted = true;
		
		for (int i = 1; i < array_length; i++){
			array_sorted = array_sorted && (test_array[i-1] <= test_array[i]);
			System.out.print(test_array[i-1] + " ");
		}
		
		System.out.println(test_array[array_length - 1] + "; ");
		System.out.println(array_sorted);
		long time = stop - start;
		System.out.println(time);
		time = (new Date()).getTime();
		time = time/1000;
		time = time/3600;
		time = time/24;
		time = time/365;
		System.out.print(time);
	}

}
